package _0600_Non_negative_Integers_without_Consecutive_Ones;

import java.util.ArrayList;
import java.util.List;

/**
 * Date: 2021/9/12 10:43
 * Content:
 * 执行用时：2 ms, 在所有 Java 提交中击败了30.20%的用户
 * 内存消耗：36.2 MB, 在所有 Java 提交中击败了11.76%的用户
 */
public class Solution {

    static final int N = 35;
    int[][] f = new int[N][2];  // f[i][j]: 一共i位，且最高位是j对应的方案数

    public int findIntegers(int n) {

        init();

        List<Integer> nums = new ArrayList<>();
        while (n != 0) {
            nums.add(n % 2);
            n /= 2;
        }
        int res = 0;
        int last = 0;  // 前一位对应的值
        for (int i = nums.size() - 1; i >= 0; i--) {
            int x = nums.get(i);

            if (x != 0) {
                res += f[i + 1][0];  // 当前为填写0对应的方案数
                if (last == 1) break;
            }
            last = x;

            if (i == 0) res++;  // n这个数也满足要求，因此需要+1
        }
        return res;
    }

    private void init() {

        f[1][0] = f[1][1] = 1;

        for (int i = 2; i < N; i++) {
            f[i][0] += f[i - 1][0] + f[i - 1][1];
            f[i][1] += f[i - 1][0];
        }
    }

    public static void main(String[] args) {

        System.out.println((new Solution()).findIntegers(5));  // 5
        System.out.println((new Solution()).findIntegers(100));  // 34
    }
}
